package com.jacky.dp;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class 最长递增子序列_300 {

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //定义一个dp数组，默认nums数组每个元素最长递增子序列为1
        int[] dp = new int[nums.length];
        //设置第一个元素递增子序列为1
        dp[0] = 1;
       //定义返回值，默认为1
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            //每遍历一个节点，判断节点前面有哪个元素比，当前元素小，如果前面有元素比当前nums[i]要小，就要
            // 把前面元素的最大递增子序列值+1（dp[j] + 1）与当前元素的最大递增子序列值dp[i]比较，取较大值
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            //dp记录着每个节点最大递增子序列，取最大值即可
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
